package LRUCache;

import java.awt.datatransfer.FlavorListener;
import java.util.*;

//1,直接继承LinkedHashmap，对于指定方法直接调用
public class MyLRUCache extends LinkedHashMap<Integer,Integer> {

    public int capacity;

    public MyLRUCache(int capacity) {
        super(capacity,0.75f,true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key,-1);
    }

    //需要重写一个方法才可以使这个LRUCache的容量固定
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }

    public void put(int key, int value) {
        super.put(key, value);
    }
}

/**
 * 自己实现LRUCache
 * 底层是hashmap和双线链表的结合
 * hashmap是时间复杂度为O(1),双向链表是为了插入方便,并处理在使用数据后的节点的
 * 先后次序
 */
class MyLRUCacheAllBySelf {

    static private final int DEFAULT_CAPACITY = 16;

    static class DListNode {
        DListNode prev;
        DListNode next;
        int val;

        public DListNode() {

        }

        public DListNode(int val) {
            this.val = val;
        }
    }

    //使用俩个哨兵节点，这样方便去插入
    DListNode head;
    DListNode tail;
    Map<Integer,DListNode> cache;//用来储存每个数据
    int capacity;
    int size;//有效数据数量

    MyLRUCacheAllBySelf() {
        //创建哨兵链表
        head = new DListNode();
        tail = new DListNode();

        head.next = tail;
        tail.prev = head;

        size = 0;
        this.capacity = DEFAULT_CAPACITY;//默认为16
        cache = new HashMap<>(DEFAULT_CAPACITY);
    }

    MyLRUCacheAllBySelf(int capacity) {
        head = new DListNode();
        tail = new DListNode();

        head.next = tail;
        tail.prev = head;

        size = 0;
        this.capacity = capacity;
        cache = new HashMap<>(capacity);
    }

    //插入数据
    public void put(int key, int val) {
        //找到这个key对饮的链表
        DListNode node = cache.get(key);
        //不存在这个数据，那么就吧这个数据mao中后直接尾插到链表中就可以了
        if (node == null) {//不存在
            //创建这个链表
            DListNode newNode = new DListNode(val);
            //如果这个map的长度大于capacity，那么要删除头节点
            if (size > capacity) {
                DListNode ret = removeHead();
                cache.remove(ret.val);
            }
            //尾插入
            addToTail(newNode);
            //将这个节点放入cache中
            cache.put(key, newNode);
        } else {
            //这个数据存在，那么要吧这个数据对应的val更改,然后把这个数据放到链表最后去
            node.val = val;//改变他的值
            //将这个节点移动到最后，因为他使用过了
            removeNodeToTail(node);
        }
    }

    public int get(int key) {
        //使用过了这个数据
        removeNodeToTail(cache.get(key));

        return cache.get(key).val;
    }

     DListNode removeHead() {
        DListNode tmp = head.next;
        head.next = tmp.next;
        head.next.prev = head;

        return tmp;
    }

    public void print() {

    }

    @Override
    public String toString() {
        StringBuffer s = new StringBuffer();
        for (DListNode node = head.next; node.next != null; node = node.next) {
            s.append(node.val+" ");
        }
        return s.toString();
    }

    //尾插
    private void removeNodeToTail(DListNode node) {
        //因为最后也会插入这个节点，所以没有从cache中移除
        //然后删除这个节点
        removeNode(node);
        //尾插这个节点，这样集移到了最后
        addToTail(node);
    }

    private void addToTail(DListNode newNode) {
        //改变next
        tail.prev.next = newNode;
        newNode.next = tail;

        //改变prev
        newNode.prev = tail.prev;
        tail.prev = newNode;

        size++;
    }

    private void removeNode(DListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

}








